'''
使用 二分法 在 python 中 // 是向下整除
 7 / 2 = 3.5
 7 // 2 = 3

二分法 记得使用 while
'''
def searchInsert(nums, target):
    ## 定义左右边界
    left = 0
    right = len(nums) - 1
    ## 开始 while
    while left <= right:
        mid = (left + right) // 2
        ##二分查找
        if nums[mid] == target:
            return mid          ##n 找到目标 返回索引
        elif nums[mid] < target:
            left  = mid +  1    ## 目标在右半部分
        else:
            right = mid - 1
    ## 跳出循环的条件是 left > right 这个时候 left 就是 target 要插入的地方
    return left

if __name__ == "__main__":
    print(searchInsert([1,3,5,6], 2))  # 输出: 1
    print(searchInsert([1,3,5,6], 7))  # 输出: 4
    print(searchInsert([1,3,5,6], 0))  # 输出: 0
    print(searchInsert([], 1)) 
    
